package com.mjlf.algorithms.sort;

/**
 * @auther a123
 * @create 2018-09-07 09:59
 * @desc 希尔排序
 * 希尔排序是插入排序的升级版， 在插入排序中，每次进行比较的步长为1，也就是每次都是与相邻的元素进行比较，
 * 如果我们使用升序排序，最小的一个元素在最后， 那么，这元素就需要与前边的每一个元素各进行一次比较，
 * 而且前边的每个元素都需要向后移动
 * 实验表明，插入排序对局部有序的序列解析排序非常有效， 所以我们可以构建这样的序列， 每次隔n个进行比较
 *
 * select sortByDown : 124
 * insert sortByDown : 66
 * shell sortByDown : 1
 *
 * select sortByDown : 108
 * insert sortByDown : 70
 * shell sortByDown : 2
 *
 * select sortByDown : 134
 * insert sortByDown : 74
 * shell sortByDown : 2
 * 根据结果显示，选着排序比插入排序慢，插入排序比希尔排序慢
 *
 */
public class ShellSort {

    public static void main(String[] args) {
        Integer[] elements = {1, 3, 2, 5, 3, 8, 4};
        sort(elements);
        SortUtil.show(elements);
    }

    public static void sort(Comparable[] elements) {

        int len = elements.length;
        int h = 1;
        while (h < len / 3) {//计算步长， 1， 4， 13
            h = h * 3 + 1;
        }
        while (h >= 1) {//对应不同步长的子序列进行插入排序

            //i < len 表示最后下边为len-1的元素也会进行到排序
            for (int i = h; i < len; i++) {
                Comparable indexElement = elements[i];
                int j = i;
                //注意这里使用不是交换式， 所以比较的元素是indexElement和element[j-h]
                //不使用交互的方法， 交互每次会多进行一次赋值
                for (; j >= h && SortUtil.less(indexElement, elements[j - h]); j -= h) {
//                    SortUtil.exch(elements, j, j - h);
                    elements[j] = elements[j - h];
                }
                elements[j] = indexElement;
            }
            h /= 3;
        }
    }
}
